GATE IT 2004
Q21.
A serial transmission T1 uses 8 information bits, 2 start bits, 1 stop bit and 1 parity bit for each character. A synchronous transmission T2 uses 3 eight-bit sync characters followed by 30 eight-bit information characters. If the bit rate is 1200 bits/second in both cases, what are the transfer rates of T1 and T2?Q22.
If f(l) = 2, f(2) = 4 and f(4) = 16, what is the value of f(3) using Lagrange's interpolation formula?Q23.
Consider the following iterative root finding methods and convergence properties: The correct matching of the methods and properties isQ24.
The semaphore variables full, empty and mutex are initialized to 0, n and 1, respectively. Process P1 repeatedly adds one item at a time to a buffer of size n, and process P2 repeatedly removes one item at a time from the same buffer using the programs given below. In the programs, K, L, M and N are unspecified statements. P1 while (1) { K; P(mutex); Add an item to the buffer; V(mutex); L; } P2 while (1) { M; P(mutex); Remove an item from the buffer; V(mutex); N; } The statements K, L, M and N are respectivelyQ25.
Let M=(K, \Sigma, \Gamma, \Delta, s, F) be a pushdown automaton, where K=(s, f), F=\{f\}, \Sigma=\{a, b\}, \Gamma=\{a\} \text { and } \Delta=\{((s, a, \epsilon),(s, a)),((s, b, \epsilon),(s, a)),((s, a, a),(f, \epsilon)),((f, a, a),(f, \epsilon)) ((f, b, a),(f, \epsilon))\}Which one of the following strings is not a member of L(M)?Q26.
Let H_1, H_2, H_3, ... be harmonic numbers. Then, for n \in Z^+, \sum_{j=1}^{n} H_j can be expressed asQ27.
Consider a list of recursive algorithms and a list of recurrence relations as shown below. Each recurrence relation corresponds to exactly one algorithm and is used to derive the time complexity of the algorithm. \begin{array}{|l|l|l|l|}\hline \text{} & \textbf{Recursive Algorithm } & \text{} & \textbf{Recurrence Relation} \\\hline \text{P} & \text{Binary search} & \text{l.} & \text{$T(n) = T(n-k) +T(k) +cn$} \\\hline \text{Q.} & \text{Merge sort} &\text{ll.} & \text{$T(n) = 2T(n-1) + 1$ }\\\hline\text{R.} & \text{Quick sort}& \text{lll.} & \text{$T(n) = 2T(n/2) + cn$}\\\hline \text{S.} & \text{Tower of Hanoi} & \text{lV.} & \text{$T(n) = T(n/2) + 1$} \\\hline \end{array}Which of the following is the correct match between the algorithms and their recurrence relations?Q28.
Let R_{1} be a relation from A =\left \{ 1,3,5,7 \right \} to B = \left \{ 2,4,6,8 \right \}. R_{2} be another relation from B to C = {1, 2, 3, 4} as defined below: i. An element x in A is related to an element y in B (under R_{1}) if x + y is divisible by 3. ii. An element x in B is related to an element y in C (under R_{2}) if x + y is even but not divisible by 3. Which is the composite relation R_{1}R_{2} from A to C?Q29.
Which one of the following regular expressions is NOT equivalent to the regular expression (a + b + c)^*?Q30.
The storage area of a disk has the innermost diameter of 10 cm and outermost diameter of 20 cm. The maximum storage density of the disk is 1400 bits/cm. The disk rotates at a speed of 4200 RPM. The main memory of a computer has 64-bit word length and 1\mu s cycle time. If cycle stealing is used for data transfer from the disk, the percentage of memory cycles stolen for transferring one word is